package com.zhanghp.class039;

import java.util.ArrayList;

/**
 * 含有嵌套的表达式求值<br/>
 * 测试链接 : https://leetcode.cn/problems/basic-calculator-iii/
 *
 * @author zhanghp
 * @since 2024/6/21 14:09
 */
public class Code01_BasicCalculatorIII {


    public static void main(String[] args) {
        int calculate = new Code01_BasicCalculatorIII().calculate("0");
        System.out.println(calculate);
    }

    public int calculate(String s) {
        // 重置where
        where = 0;
        return f(s.toCharArray(), 0);
    }


    public static int where;

    public static int f(char[] c, int i) {
        int cur = 0;
        // 数字栈
        ArrayList<Integer> nums = new ArrayList<>();
        // 符号栈
        ArrayList<Character> ops = new ArrayList<>();

        // 字符与 ')' 做匹配，用来告诉当前嵌套的括号运算已经处理完
        while (i < c.length && c[i] != ')') {
            // 数字处理 [0,9]
            if (c[i] >= '0' && c[i] <= '9') {
                // 之前数字乘10，字符ascII码进行处理
                cur = cur * 10 + (c[i++] - '0');

            }else if(c[i] == '('){

                //嵌套处理
                // i+1,代表嵌套处理的递归调用，相当于括号内的正常计算，返回结果
                // 多层嵌套，多次调用计算，可以这么理解
                // 进行cur的赋值，对于嵌套的结果
                cur =  f(c, i + 1);
                i = where + 1;

            }else {

                // 符号处理 & 进行压榨 & 索引递增
                push(cur, c[i++], nums, ops);
                cur = 0;

            }

        }
        // 打破while，最后一个cur是没处理的，所以要压入栈中
        push(cur, '+', nums, ops);
        // 在返回之前，进行where设置（若涉及多重嵌套，则告诉上一层的递归嵌套，哪个位置是此嵌套的末尾）
        where = i;
        // 返回计算结果
        return comput(nums, ops);
    }

    /**
     * 进行 数字 和 符号的压栈
     *
     * @param num 数字
     * @param op 符号
     * @param nums 数字集合
     * @param ops 符号集合
     */
    public static void push(int num, char op, ArrayList<Integer> nums, ArrayList<Character> ops) {
        int n = nums.size();
        // 若是空 || 上一层的运算符是+ || 上一层的运算符是-
        if (n == 0 || ops.get(n - 1) == '+' || ops.get(n - 1) == '-') {
            nums.add(num);
            ops.add(op);
        } else {
            // 进行上一层有 * 或 ÷ 进行数据处理，并替代
            Integer topNumber = nums.get(n - 1);
            char topOp = ops.get(n - 1);
            if (topOp == '*') {
                nums.set(n - 1, topNumber * num);
            } else {
                nums.set(n - 1, topNumber / num);
            }
            ops.set(n - 1, op);
        }
    }

    /**
     * 计算 数字栈 和 符号栈的结果
     *
     * @param nums 数字集合
     * @param ops 符号集合
     * @return 结果
     */
    public static int comput(ArrayList<Integer> nums, ArrayList<Character> ops) {
        int n = nums.size();
        // 需要先获取数字，然后进行符号的获取处理，不能设置为0
        int ans = nums.get(0);
        for (int i = 1; i < n; i++) {
            ans += ops.get(i - 1) == '+' ? nums.get(i) : -nums.get(i);
        }
        return ans;
    }



}
